package org.czl.gh;

import java.util.HashMap;

public class l2709 {
    public static void main(String[] args) {
        System.out.println(canTraverseAllPairs(new int[]{3, 9, 5}));
    }
    static int[] father;
    static int size;
    public static boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        size = n;
        father = new int[n + 2];
        for(int i = 0; i < n; i++){
            father[i] = i;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            int cur = nums[0];
            for(int j = 2; j * j <= cur; j++){
                if(cur % j == 0){
                    if(!map.containsKey(j)){
                        map.put(j, i);
                    }else{
                        union(i, map.get(j));
                    }
                }
                while(cur % j == 0){
                    cur /= j;
                }
            }
            if(cur > 1){
                if(!map.containsKey(cur)){
                    map.put(cur, i);
                }else{
                    union(i, map.get(cur));
                }
            }
        }
        return size == 1;
    }
    static int find(int x){
        if(x != father[x]){
            father[x] = find(father[x]);
        }
        return father[x];
    }
    static void union(int x, int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            father[fx] = fy;
            size--;
        }
    }
}
